In recent years, in forwarding processing units of packet switching systems, in response to the demand for network integration, simultaneous realization of L2 (layer 2 switch), VLAN (virtual LAN), MPLS (multi-protocol label switching), PW (pseudo wire), IP (Internet protocol), and other various forwarding processing has been sought.
As techniques to realize these, a FPGA (field programmable gate array), LSI (large scale integrated circuit), and other hardware-based forwarding techniques having superiority in high speed, software processing-based forwarding techniques having superiority in flexibility, and other programmable chip-based forwarding techniques etc. as their intermediate NPU (network processor unit) may be mentioned. In these various techniques, the basic performance requirements demanded are high throughput, flexibility, and programmability.
The embodiments took note of the performance of the look-up processing in the memory contained in the forwarding unit so as to achieve high throughput, flexibility, programmability of a forwarding processing unit in a packet switching system regardless of the technique mentioned above.
Regardless of the technique for realizing the forwarding processing unit in a packet switching system, the forwarding processing unit must perform table look-up processing. A table in the forwarding processing unit is arranged outside or inside a chip forming the forwarding processing unit. Packet header information and a receiving port number, etc. are used as the address for each input packet to look up a series of tables and perform usual packet processing. In this case, to achieve 100% throughput of input packets (wire speed processing), each table look-up operation must be completed within a limited time interval.
If, in one table look-up operation, packets are input at a rate greater than the maximum possible access rate with which the table memory can be accessed, 100% throughput cannot be achieved. For this reason, the number of clock cycles necessary for one table look-up operation for packets needs to be kept within a certain range.
As related art, there is the invention described in Patent Document 1. This document discloses the art of automatically loading addresses of traffic particularly heavy in load or exceeding a threshold value predicted and set in advance in a detailed table in the forwarding tables, but does not disclose keeping the number of clock cycles necessary for one table look-up operation for packets within a certain range.
Patent Document 1: Japanese Laid-Open Patent Publication No. 2005-117214
FIG. 3 is a block diagram showing the relationship between a conventional sequence number memory and a forwarding processing unit for explaining the problem to be solved by the embodiments. In FIG. 3, 31 indicates a sequence number memory, 32 a memory interface unit, and 33 a forwarding processing unit. In a PW or other packet switching system, the sequence of packets for voice data, music data, etc. is crucial. The data becomes meaningless if the sequence of packets is jumbled. To maintain the packet sequence, a sequence number is assigned to each pseudo wire (PW) having a control (see FIG. 6). In FIG. 3, the current sequence numbers 0x0005, 0x007C, . . . , 0x0EA5 corresponding to the PW addresses (1), (2), . . . (n) are stored in the sequence number memory 31. Note that, the “0x”s at the heads of the sequence numbers signify, as is common knowledge, that the following numerical values are hexadecimal.
The forwarding processing unit 33 accesses the sequence number memory 31 at the nth (wherein n is a positive integer) access point which follows the n−1th forwarding processing. The memory interface unit 32, responding to the access, carries out (1) reading, (2) addition, (3) comparison, (4) round up, and (5) write back processing operations. Of these, (3) and (4) are executed only when, as will be detailed later, the sequence number is a specific value.
The forwarding processing unit 33 runs forwarding processing based on the processing results by the memory interface unit 32 and outputs the results as output packets.
The first step, in a table look-up operation for an usual forwarding processing unit 33, referring to the sequence number memory 31 is the (1) read processing with respect to the sequence number memory 31. In this processing, reading a sequence number stored in the sequence number memory 31 is read by using as an address the header information of an input packet. This processing is carried out for each input packet, therefore the higher the rate of input packets, the higher the access rate to the sequence number memory 31 demanded. Generally, the higher speed of the band of the sequence number memory 31 can be attained by increasing the number of operating clocks of the sequence number memory 31, increasing the number of data bits, etc.
Here, the problem to be addressed is that when processing does not conclude by just reading from the sequence number memory 31, but certain judgment is required and the result of judgment has to be written back, based on the read sequence number, into the same memory space as the read out memory space, wherein the processing will sometimes not be completed within “the number of consumed clock cycles which one read processing operation must observe to achieve 100% throughput of wire speed processing”.
Specifically, in processing of adding a 16-bit sequence number, defined by a control word supported by pseudo wire (PW) packets, to a PW frame, as shown in the memory interface unit 32, the series of processing operations of (1) reading the sequence number stored in the sequence number memory 31 for read processing, (2) adding 1 to the read sequence number for addition processing, and (5) writing back the result of addition to the same memory space as the memory space from which the result of addition was read. However, according to processing conforming to the RFC standard, the number after the sequence number=0xFFFF is not 0xFFFF+1=0x0000 but 0xFFFF+2=0x0001 (referred to as “roundup processing” here), where 0x0000 must be skipped. This is because in the RFC standard for a pseudo wire, the sequence number=0x0000 is defined as meaning “sequence number not used”. In this case, the series of processing operations, i.e. (1) reading, (3) comparison, (2) or (4) addition or round up, and (5) write back processing operations is necessary. Keeping these processing operations within a certain number of clock cycles, that is allowable for one access to a table, is, however, extremely difficult.
Accordingly, it is an object of the embodiments to enable completion of the necessary processing within a certain number of clock cycles allowed for one access to a table in a forwarding processing unit of a packet switching system.